#include "Radix.h"

void Radix::insert(unsigned int bits, unsigned int bitCount, unsigned int position)
{
    if (bitCount == 0)
    {
        delete m_root;
        m_root = new ExtNode(position);
        return;
    }

    if (m_root == NULL || m_root->getBucketPosition() != -1)
    {
        delete m_root;
        m_root = new IntNode();
    }

    ExtNode * currentNode = m_root;

    unsigned int mask = 1;
    unsigned int digit = bits & mask;

    for(unsigned int i = 0; i < bitCount - 1; i++)
    {
        if (digit == 0)
        {
            ExtNode * leftChild = currentNode->getLeftChild();

            if (leftChild == NULL || leftChild->getBucketPosition() != -1)
            {
                delete leftChild;
                currentNode->setLeftChild(new IntNode());
            }

            currentNode = currentNode->getLeftChild();
        }
        else if (digit == 1)
        {
            ExtNode * rightChild = currentNode->getRightChild();

            if (rightChild == NULL || rightChild->getBucketPosition() != -1)
            {
                delete rightChild;
                currentNode->setRightChild(new IntNode());
            }

            currentNode = currentNode->getRightChild();
        }

        bits = bits >> 1;
        digit = bits & mask;
    }

    if (digit == 0)
        currentNode->setLeftChild(new ExtNode(position));
    else if (digit == 1)
        currentNode->setRightChild(new ExtNode(position));
}

int Radix::retrieve(unsigned int articleNumber)
{
    unsigned int hashCode = articleNumber % m_divisor;

    ExtNode * currentNode = m_root;

    if (currentNode == NULL)
        return -1;

    if (currentNode->getBucketPosition() != -1)
        return m_root->getBucketPosition();

    unsigned int mask = 1;
    unsigned int currentBit = hashCode & mask;

    while(true)
    {
        if(currentBit == 0)
            currentNode = currentNode->getLeftChild();
        else if(currentBit == 1)
            currentNode = currentNode->getRightChild();

        if (currentNode == NULL || currentNode->getBucketPosition() != -1)
            break;

        hashCode = hashCode >> 1;
        currentBit = hashCode & mask;
    }

    if (currentNode == NULL)
        return -1;

    return currentNode->getBucketPosition();
}

int Radix::getDepth(unsigned int articleNumber)
{
    unsigned int hashCode = articleNumber % m_divisor;
    int depth = 0;

    ExtNode * currentNode = m_root;

    if (currentNode == NULL)
        return -1;

    if (currentNode->getBucketPosition() != -1)
        return depth;

    unsigned int mask = 1;
    unsigned int currentBit = hashCode & mask;

    while(true)
    {
        depth++;

        if (currentBit == 0)
            currentNode = currentNode->getLeftChild();
        else if (currentBit == 1)
            currentNode = currentNode->getRightChild();

        if (currentNode==NULL || currentNode->getBucketPosition()!= -1)
            break;

        hashCode = hashCode >> 1;
        currentBit = hashCode & mask;
    }

    return depth-1;
}
